<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="Hexo Theme Keep">
    <meta name="description" content="Hexo Theme Keep">
    <meta name="author" content="cheng5.du">
    
    <title>
        
            二叉树深度和广度优先遍历 |
        
        cheng5.du
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="/images/avatar.jpeg">
    
<link rel="stylesheet" href="/css/font-awesome.min.css">

    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"example.com","root":"/","language":"zh-CN"};
    KEEP.theme_config = {"toc":{"enable":false,"number":false,"expand_all":false,"init_open":false},"style":{"primary_color":"#0066CC","avatar":"/images/avatar.jpeg","favicon":"/images/avatar.jpeg","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":false},"first_screen":{"enable":true,"background_img":"/images/bg.svg","description":"人生海海，来日方长。"},"scroll":{"progress_bar":{"enable":false},"percent":{"enable":false}}},"local_search":{"enable":false,"preload":false},"code_copy":{"enable":false,"style":"default"},"pjax":{"enable":false},"lazyload":{"enable":false},"version":"3.4.5"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 个月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 6.1.0"></head>


<body>
<div class="progress-bar-container">
    

    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                cheng5.du
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/tags"
                            >
                                标签
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/netease"
                            >
                                网抑云
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于我
                            </a>
                        </li>
                    
                    
                </ul>
            </div>
            <div class="mobile">
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/tags">标签</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/netease">网抑云</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于我</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">二叉树深度和广度优先遍历</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="/images/avatar.jpeg">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">cheng5.du</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;
        <span class="pc">2021-05-27 11:04:55</span>
        <span class="mobile">2021-05-27 11:04</span>
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/">数据结构与算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/%E4%BA%8C%E5%8F%89%E6%A0%91/">二叉树</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
    
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <h2 id="树"><a href="#树" class="headerlink" title="树"></a>树</h2><blockquote>
<p>树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。</p>
</blockquote>
<p><img src="https://cdn.jsdelivr.net/gh/superFatDu/blogPics@main/20210609/%E6%A0%91.6a9nbdfcvdg0.png" alt="树"></p>
<h3 id="树的节点"><a href="#树的节点" class="headerlink" title="树的节点"></a>树的节点</h3><h4 id="节点"><a href="#节点" class="headerlink" title="节点"></a>节点</h4><p>使用树结构存储的每一个数据元素都称为“节点”。如A就是一个节点。</p>
<h4 id="树根节点"><a href="#树根节点" class="headerlink" title="树根节点"></a>树根节点</h4><p>简称“根节点”，每一个非空树都有且有一个被称为根的节点，比如A。</p>
<h4 id="父节点（双亲节点），子节点和兄弟节点"><a href="#父节点（双亲节点），子节点和兄弟节点" class="headerlink" title="父节点（双亲节点），子节点和兄弟节点"></a>父节点（双亲节点），子节点和兄弟节点</h4><ol>
<li>有子节点的节点为父节点，如A,B,C,D,E,H都是父节点。</li>
<li>B,C,D是A的子节点；E,F是B的子节点……</li>
<li>同一父节点的同一层节点是兄弟节点。如B,C,D是兄弟节点。</li>
</ol>
<h4 id="叶子结点"><a href="#叶子结点" class="headerlink" title="叶子结点"></a>叶子结点</h4><p>如果节点没有任何子节点，那么此节点称为“叶子节点”。比如K,L,F,G,M,I,J</p>
<h3 id="度和层次"><a href="#度和层次" class="headerlink" title="度和层次"></a>度和层次</h3><h4 id="度"><a href="#度" class="headerlink" title="度"></a>度</h4><p>对于一个节点，拥有的子树数称为节点的度（Ddgree）。如A的度为3</p>
<h4 id="层次"><a href="#层次" class="headerlink" title="层次"></a>层次</h4><p>以根节点为第一层，然后子节点为一层，孙子节点为一层，以此类推。如图树有4层。</p>
<h5 id="深度"><a href="#深度" class="headerlink" title="深度"></a>深度</h5><p>树中节点所在的最大的层数，就是树的深度。如图树的深度为4。</p>
<h3 id="深度和广度优先遍历"><a href="#深度和广度优先遍历" class="headerlink" title="深度和广度优先遍历"></a>深度和广度优先遍历</h3><p><img src="https://cdn.jsdelivr.net/gh/superFatDu/blogPics@main/20210609/%E5%B9%BF%E5%BA%A6%E6%B7%B1%E5%BA%A6.4g9bfc07kqg0.png" alt="广度深度"></p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> tree = &#123;</span><br><span class="line">  <span class="attr">val</span>: <span class="string">&#x27;a&#x27;</span>,</span><br><span class="line">  <span class="attr">children</span>: [</span><br><span class="line">    &#123;</span><br><span class="line">      <span class="attr">val</span>: <span class="string">&#x27;b&#x27;</span>,</span><br><span class="line">      <span class="attr">children</span>: [</span><br><span class="line">        &#123;</span><br><span class="line">          <span class="attr">val</span>: <span class="string">&#x27;d&#x27;</span>,</span><br><span class="line">          <span class="attr">children</span>: []</span><br><span class="line">        &#125;,</span><br><span class="line">        &#123;</span><br><span class="line">          <span class="attr">val</span>: <span class="string">&#x27;e&#x27;</span>,</span><br><span class="line">          <span class="attr">children</span>: []</span><br><span class="line">        &#125;</span><br><span class="line">      ]</span><br><span class="line">    &#125;,</span><br><span class="line">    &#123;</span><br><span class="line">      <span class="attr">val</span>: <span class="string">&#x27;c&#x27;</span>,</span><br><span class="line">      <span class="attr">children</span>: [</span><br><span class="line">        &#123;</span><br><span class="line">          <span class="attr">val</span>: <span class="string">&#x27;f&#x27;</span>,</span><br><span class="line">          <span class="attr">children</span>: []</span><br><span class="line">        &#125;,</span><br><span class="line">        &#123;</span><br><span class="line">          <span class="attr">val</span>: <span class="string">&#x27;g&#x27;</span>,</span><br><span class="line">          <span class="attr">children</span>: []</span><br><span class="line">        &#125;</span><br><span class="line">      ]</span><br><span class="line">    &#125;</span><br><span class="line">  ]</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="深度优先遍历"><a href="#深度优先遍历" class="headerlink" title="深度优先遍历"></a>深度优先遍历</h4><ol>
<li>输出节点</li>
<li>遍历children</li>
</ol>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> <span class="title function_">dfs</span> = root =&gt; &#123;</span><br><span class="line">  <span class="variable language_">console</span>.<span class="title function_">log</span>(root.<span class="property">val</span>)</span><br><span class="line">  root.<span class="property">children</span>.<span class="title function_">forEach</span>(dfs)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="广度优先遍历"><a href="#广度优先遍历" class="headerlink" title="广度优先遍历"></a>广度优先遍历</h4><ol>
<li>新建一个队列</li>
<li>将队头的数据出队</li>
<li>将children放进队列</li>
</ol>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> <span class="title function_">bfs</span> = root =&gt; &#123;</span><br><span class="line">  <span class="keyword">const</span> queue = []</span><br><span class="line">  <span class="keyword">while</span>(queue.<span class="property">length</span>) &#123;</span><br><span class="line">    <span class="keyword">const</span> n = queue.<span class="title function_">shift</span>()</span><br><span class="line">    <span class="variable language_">console</span>.<span class="title function_">log</span>(n.<span class="property">val</span>)</span><br><span class="line">    n.<span class="property">children</span>.<span class="title function_">forEach</span>(<span class="function"><span class="params">child</span> =&gt;</span> &#123;</span><br><span class="line">      queue.<span class="title function_">push</span>(child)</span><br><span class="line">    &#125;)</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

        </div>

        

        
            <ul class="post-tags-box">
                
                    <li class="tag-item">
                        <a href="/tags/%E4%BA%8C%E5%8F%89%E6%A0%91/">#二叉树</a>&nbsp;
                    </li>
                
            </ul>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2021/06/05/%E4%BD%A0%E7%9F%A5%E9%81%93%E7%9A%84Vuex/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">你知道的Vuex</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2021/05/22/%E6%B8%85%E7%A9%BA%E6%95%B0%E7%BB%84%E7%9A%84%E5%87%A0%E7%A7%8D%E6%96%B9%E6%B3%95/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">清空数组的几种方法</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2020</span>
              -
            
            2023&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">cheng5.du</a>
        </div>
        
        <div class="theme-info info-item">
            Powered by <a target="_blank" href="https://hexo.io">Hexo</a>&nbsp;|&nbsp;Theme&nbsp;<a class="theme-version" target="_blank" href="https://github.com/XPoet/hexo-theme-keep">Keep v3.4.5</a>
        </div>
        
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        

        <!-- go comment -->
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="fas fa-arrow-up"></i>
            </li>
        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
    </ul>
</div>

    </div>

    

    <div class="image-viewer-container">
    <img src="">
</div>


    

</main>




<script src="/js/utils.js"></script>

<script src="/js/main.js"></script>

<script src="/js/header-shrink.js"></script>

<script src="/js/back2top.js"></script>

<script src="/js/dark-light-toggle.js"></script>








<div class="post-scripts">
    
</div>



</body>
</html>
